P4464 [国家集训队]JZPKIL 发布于 2020-09-12 | 分类于 莫比乌斯反演 、 伯努利数 | 11分钟 | 1781字数 如果不知道伯努利数的点这里。 ∑i=1n(i,n)x[i,n]y\sum_{i=1}^n (i,n)^x[i,n]^y i=1∑n(i,n)x[i,n]y 阅读全文 »
P1587 [NOI2016]循环之美 发布于 2020-09-12 | 分类于 莫比乌斯反演 | 5分钟 | 764字数 类比十进制下的纯循环小数,kkk 进制下的纯循环小数满足最简分数分母与 kkk 互质。 而题目要求相同数值只计数一次,所以只需要考虑最简分数的情况。 那么答案为: 阅读全文 »
P2480 [SDOI2010]古代猪文 发布于 2020-09-12 | 分类于 数论 | 4分钟 | 515字数 g∑d∣nCnn/dmod 999911659g^{\sum_{d|n}C_{n}^{n/d}} \mod 999911659 g∑d∣nCnn/dmod999911659 g∑d∣nCndmod 999911659g^{\sum_{d|n}C_{n}^{d}} \mod 999911659 阅读全文 »
P5769 [JSOI2016]飞机调度 发布于 2020-09-12 | 分类于 网络流 | 5分钟 | 758字数 网络流24题 为了使飞机数量尽量少,一架飞机尽量多飞几趟航班。 将航班看成一个点,其实就是求最小路径覆盖。 阅读全文 »
P2303 [SDOI2012] Longge 的问题 发布于 2020-09-12 | 分类于 数论 、 欧拉函数 | 2分钟 | 266字数 ∑i=1n(i,n)\sum_{i=1}^n(i,n) i=1∑n(i,n) ∑d∣nd∑i=1n[(i,n)=d]\sum_{d|n}d\sum_{i=1}^n[(i,n)=d] 阅读全文 »
P5130 纯粹的弹幕地狱 发布于 2020-09-12 | 分类于 数论 、 欧拉函数 | 6分钟 | 967字数 因为每回合击中的概率是固定的,所以只需要算一次。 概率为:可以击中的情况/总情况。 每个点有 (n+1)2(n+1)^2(n+1)2 个位置,所以总情况为(n+1)4(n+1)^4(n+1)4 阅读全文 »
P5451 [THUPC2018]密码学第三次小作业 发布于 2020-09-12 | 分类于 莫比乌斯反演 | 3分钟 | 417字数 如果你做过 P4358 [CQOI2016]密钥破解 ,那么你基本上就凉了。 这道题跟背景没有任何关系。 注意到二元不定方程: xe1+ye2=(e1,e2)=1xe1+ye2=(e1,e2)=1xe1+ye2=(e1,e2)=1 阅读全文 »
P3312 [SDOI2014]数表 发布于 2020-09-12 | 分类于 莫比乌斯反演 | 5分钟 | 758字数 ∑i=1n∑j=1mσ((i,j))\sum_{i=1}^n\sum_{j=1}^m \sigma((i,j)) i=1∑nj=1∑mσ((i,j)) ∑d=1min(n,m)σ(d)∑i=1n∑j=1m[gcd(i,j)=d]\sum_{d=1}^{\min(n,m)}\sigma(d)\sum_{i=1}^n\sum_{j=1}^m [gcd(i,j)=d] 阅读全文 »
P6055 [RC-02] GCD 发布于 2020-09-12 | 分类于 莫比乌斯反演 | 3分钟 | 471字数 这道题的反推还是挺有意思的。 ∑i=1n∑j=1n∑p=1⌊nj⌋∑q=1⌊nj⌋[(i,j)=1][(p,q)=1]\sum_{i=1}^n\sum_{j=1}^n\sum_{p=1}^{\lfloor \frac{n}{j} \rfloor}\sum_{q=1}^{\lfloor \frac{n}{j} \rfloor}[(i,j)=1][(p,q)=1] i=1∑nj=1∑np=1∑⌊jn⌋q=1∑⌊jn⌋[(i,j)=1][(p,q)=1] 阅读全文 »